package com.zk.algorithm.others;

import com.zk.algorithm.Utils;
import com.zk.algorithm.annotation.JianZhiOffer;

import java.util.Stack;

/**
 * 栈的压入、弹出序列
 *
 * 第一个序列：表示栈的压入顺序
 * 第二个序列：表示栈的弹出顺序
 *
 * 判断第二个序列是否是第一个序列的弹出顺序
 */
@JianZhiOffer("31")
public class StackPopOrder {

    public boolean isPopOrder(int[] push, int[] pop) {
        boolean possible = false;

        if (push != null && pop != null) {
            // 借助一个辅助栈
            Stack<Integer> stack = new Stack<>();

            int pushIndex = 0;
            int popIndex = 0;

            while (popIndex < pop.length) {

                // 下一个弹出的数字 pop[popIndex] 不在栈顶
                // 则一直把压栈序列中的数字压栈
                while (stack.isEmpty() || stack.peek() != pop[popIndex]) {
                    if (pushIndex == push.length) {
                        break;
                    }

                    stack.push(push[pushIndex++]);
                }

                if (stack.peek() != pop[popIndex]) {
                    break;
                }

                // 直接弹出
                stack.pop();
                popIndex++;
            }

            if (stack.isEmpty() && popIndex == pop.length) {
                possible = true;
            }
        }

        return possible;
    }

    public static void main(String...args) {
        StackPopOrder stackPopOrder = new StackPopOrder();

        Utils.println(stackPopOrder.isPopOrder(new int[] {
                1,2,3,4,5
        }, new int[]{
                4,5,3,2,1
        }));

        Utils.println(stackPopOrder.isPopOrder(new int[] {
                1,2,3,4,5
        }, new int[]{
                4,3,5,1,2
        }));
    }

}